package offer.day24;

public class No39MoreThanHalfNum {
    /*
     * 面试题39：数组中出现次数超过一半的数字
     * 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 例如：输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}.
     * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2
     *
     *
     * 思路：Partition方法
     * 将数组进行排序，若是某个数字在数组中超过一半，
     *那么排序后的中间位置的数字就是要找的那个重复的数字
     *使用快速排序的方法，将其进行排序  找到中间的，
     *并且使用一个函数再对该数字进行检验，查看重复量是否超过了一半
     *
     * */
    //int flag = 0;
    //标志位（当number=0时）  ：若flag为0  表示数组不为空   若flag为1  表示数组为空
    public static void main(String[] args) {
        No39MoreThanHalfNum m = new No39MoreThanHalfNum();
        int[] array = {1,2,3,2,2,2,5,4,2};
        System.out.println("数组中超过一半的数字是："+m.MoreThanHalfNum_Solution(array));
    }

    private int MoreThanHalfNum_Solution(int[] array){
        quickSort(array);
        int mid=array.length/2;
        return array[mid];

    }

    private void quickSort(int[] array){
        if(array==null||array.length==0) return ;
        quickSort(array,0,array.length-1);
    }

    private void quickSort(int[] array, int lo, int hi) {
        if(lo>=hi) return;
        int j=partition(array,lo,hi);
        quickSort(array,lo,j-1);
        quickSort(array,j+1,hi);
    }

    private int partition(int[] array,int low,int high){
        int val=array[low];
        int i=low+1;
        int j=high;
        while(i<=j) {
            while (i <= high && array[i] < val) {
                i++;
            }
            while (j >= low && array[j] > val) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(array, i++, j--);
        }
        swap(array,low,j);
        return j;
    }

    private void swap(int[] array,int indexA,int indexB){
        int temp=array[indexA];
        array[indexA]=array[indexB];
        array[indexB]=temp;
    }
}
